It is well understood that disc access times have not developed at the same rate as the CPU speeds and, accordingly, the difference in performance results in disc input/output operations being a bottleneck in the overall performance of computers. Two main techniques have been developed within the art to mitigate the effect of this performance gap. These two techniques are caching and prefetching. Caching involves maintaining data in memory that is most likely to be used again within a relatively short period of time. Prefetching involves reading data into memory in advance, and in anticipation, of it being used. Both techniques are widely used at the block level. Also, access patterns relating to relatively recent accesses can be used to influence future caching and prefetching of entire files.
Referring to FIG. 1, there is shown a computer system 100 comprising a file system 102 for servicing an application, i.e., dealing with data read/write disc operations associated with that application 104. When performing disc operations, the application 104 requests files from a disc drive 106 without regard to the size of those files, that is, arbitrarily large amounts of data can be requested by an application from a disc drive 106 or physical disc 118. To process such an application-level request, the file system 102 of an operating system 108 typically divides the request into a number of block size and block aligned requests.
The file system 102, when servicing the application-level request, will determine whether or not a block corresponding to one of the file system block requests is resident in an operating system cache memory 110. If the requested block is resident in the operating system cache memory 110, and it is valid, that block is retrieved and forwarded to the application 104. If the requested block is not resident in memory 110, the file system 102 issues a block request to a disc device driver 112 of the disc drive 106. The disc device driver 112 forwards the request to a disc controller 114 of the disc drive 106. The controller 114 determines whether or not the requested block is validly stored in a disc cache 116. If so, the block is retrieved from the cache 116 and forwarded to the application 104. If not, the disc controller 114 retrieves the requested block from a physical disc 118 of the disc drive 106.
It will be appreciated that prefetching files or blocks may be performed at the same time as fetching a block or file, that is, data, requested by the application 104. Therefore, the file system 102 may prefetch, for example, one block or more than one subsequent block from the disc drive 106 in anticipation of that subsequent block or those blocks being used by the application. The amount of data the file system 102 prefetches is determined by the file system's prefetch policy and may also be related to both a current of file offset and whether or not the application has been accessing data sequentially, for example. It will be appreciated that a read operation in relation to a block x from a file is sequential if the last block operation from that file was in relation to block x−1. It can be appreciated that such sequential operations represent a form of a sequential file access pattern.
One skilled in the art appreciates that file system accesses are typically pattern based and are such that the patterns can be classified as being sequential patterns, looping patterns, temporarily-clustered patterns and probabilistic reference patterns. Knowledge of such file access patterns is useful in designing a prefetch policy to improve overall performance of disc operations and, in particular, read operations.
However, each access pattern and any policy designed based on that access pattern has advantages and disadvantages. Furthermore, buffer replacement can also influence the overall performance of the computer. Still further, while some file prefetch policies are dynamic, the same policy is imposed on all files regardless of the individual requirements of a file.
It is an object of embodiments of the present invention to at least mitigate some of the problems of the prior art.